{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Make Array Zero by Subtracting Equal Amounts"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #hash-table #sorting #simulation #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #哈希表 #排序 #模拟 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumOperations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使数组中所有元素都等于零"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个非负整数数组 <code>nums</code> 。在一步操作中，你必须：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选出一个正整数 <code>x</code> ，<code>x</code> 需要小于或等于 <code>nums</code> 中 <strong>最小</strong> 的 <strong>非零</strong> 元素。</li>\n",
    "\t<li><code>nums</code> 中的每个正整数都减去 <code>x</code>。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回使 <code>nums</code> 中所有元素都等于<em> </em><code>0</code> 需要的 <strong>最少</strong> 操作数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,5,0,3,5]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>\n",
    "第一步操作：选出 x = 1 ，之后 nums = [0,4,0,2,4] 。\n",
    "第二步操作：选出 x = 2 ，之后 nums = [0,2,0,0,2] 。\n",
    "第三步操作：选出 x = 2 ，之后 nums = [0,0,0,0,0] 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [0]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>nums 中的每个元素都已经是 0 ，所以不需要执行任何操作。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 100</code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [make-array-zero-by-subtracting-equal-amounts](https://leetcode.cn/problems/make-array-zero-by-subtracting-equal-amounts/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [make-array-zero-by-subtracting-equal-amounts](https://leetcode.cn/problems/make-array-zero-by-subtracting-equal-amounts/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,5,0,3,5]', '[0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "\n",
    "        if not nums:\n",
    "            return 0\n",
    "        \n",
    "        return len(set(nums) - {0})\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        ans = 0\n",
    "        while nums:\n",
    "            while nums and nums[-1] == 0:\n",
    "                del nums[-1]\n",
    "            if not nums:\n",
    "                return ans\n",
    "            nums = [i-nums[-1] for i in nums]\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        return len(set(nums)-{0})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        return len(set(nums)-{0})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        nums=list(set(nums))\n",
    "        return len(nums)-nums.count(0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "         return len(set(nums) - {0})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        a = set(nums)\n",
    "        ans = 0\n",
    "        for n in a:\n",
    "            if n > 0:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        s = set(nums)\n",
    "        if 0 in s: s.remove(0)\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        return len(set(nums) - {0})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        return len({x for x in nums if x})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        return len(set(nums) - set([0]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "      # filter 0\n",
    "      # find min\n",
    "      count = 0\n",
    "\n",
    "      while len(nums) > 0:\n",
    "        nums = list(filter(lambda x:x>0, nums))\n",
    "\n",
    "        if len(nums) > 0:\n",
    "          _min = min(nums)\n",
    "\n",
    "          nums = [ x - _min for x in nums]\n",
    "          count += 1\n",
    "        else:\n",
    "          break\n",
    "      \n",
    "      return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        s = set(nums)\n",
    "        return len(s)-(0 in s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        dic = set()\n",
    "        for n in nums:\n",
    "            if n:\n",
    "                dic.add(n)\n",
    "        return len(dic)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        return len(set(nums) - {0})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        a = set(nums)\n",
    "        n = len(a)\n",
    "        if 0 in a:\n",
    "            n -= 1\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        # length = len(nums)\n",
    "        # count=0\n",
    "        # nums.sort()\n",
    "        # for i in range(length):\n",
    "        #     if nums[i]>0:\n",
    "        #         tmp=nums[i]                \n",
    "        #         for j in range(i,length):\n",
    "        #             nums[j]-=tmp\n",
    "        #         count+=1\n",
    "        # return count\n",
    "        return len(set(nums)-{0})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        c = Counter(nums)\n",
    "        return len(c.keys()) - (0 in c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        return len({n for n in nums if n})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        return len({x for x in nums if x})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        i,j=0,0\n",
    "        for a in nums:\n",
    "            if a>i:\n",
    "                j+=1\n",
    "                i=a\n",
    "        return j\n",
    "                        \n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        c=collections.Counter(nums)\n",
    "        c[0]=0\n",
    "        del c[0]\n",
    "        return len(list(c.keys()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        s = set([x for x in nums if x != 0])\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        return len(set(nums) - {0})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        return len(set(nums) - {0})\n",
    "        # # 由于每一次对于相同元素的操作是一样的，所以可以用set进行去重\n",
    "        # # 如果0不位于set中，则最小操作次数就等于set的长度（从最小的元素开始依次减）\n",
    "        # # 如果0位于set中，则最小操作次数就等于set的长度-1，因为元素0并不需要操作，需要排除\n",
    "        # set_num = set(nums)\n",
    "        # return len(set_num) if 0 not in set_num else len(set_num) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        # count = 0\n",
    "        # nums_sorted = sorted(nums,reverse = True) \n",
    "        # mark_num = 0\n",
    "        # i = 0\n",
    "        # while i<len(nums_sorted):\n",
    "        #     if nums_sorted[i] != 0:\n",
    "        #         if nums_sorted[i] != mark_num:\n",
    "        #             mark_num = nums_sorted[i]\n",
    "        #             count += 1\n",
    "        #             i += 1\n",
    "        #         else:\n",
    "        #             i += 1\n",
    "        #     else:\n",
    "        #         break \n",
    "        # return count\n",
    "        return len({x for x in nums if x})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        return len(set(x for x in nums if x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        while nums[-1] != 0:\n",
    "            i = 0\n",
    "            while nums[i] == 0:\n",
    "                i += 1\n",
    "            n = nums[i]\n",
    "            for j in range(i, len(nums)):\n",
    "                nums[j] -= n\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        return len(set([ i for i in nums if i ]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        nums = list(set(nums))\n",
    "        if 0 in nums:\n",
    "            nums.remove(0)\n",
    "        return len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        return len(set(nums) - {0})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        if 0 in set(nums):\n",
    "            return len(set(nums))-1\n",
    "        else:\n",
    "            return len(set(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        if sum(nums)==0:\n",
    "            return 0\n",
    "        n=len(set(nums))\n",
    "        if min(nums)==0:\n",
    "            return n-1\n",
    "        else:\n",
    "            return n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        nums = list(set(nums))\n",
    "        nums.sort()\n",
    "        if nums[0] == 0:\n",
    "            nums.pop(0)\n",
    "        return nums.__len__() "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        return len(list(set(nums)-{0}))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        return len(set(n for n in nums if n > 0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        cnt = 0\n",
    "        while nums[-1] != 0:\n",
    "            temp = 0\n",
    "            while not temp:\n",
    "                temp = nums.pop(0)\n",
    "            for i in range(len(nums)):\n",
    "                nums[i] -= temp\n",
    "            cnt += 1\n",
    "            if not nums:\n",
    "                return cnt\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        return len(set(nums) - {0})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        cnt = 0\n",
    "        minus = 0\n",
    "        while nums and nums[-1] != 0:\n",
    "            temp = 0\n",
    "            while not temp:\n",
    "                temp = nums.pop(0)\n",
    "            minus += temp\n",
    "            cnt += 1\n",
    "            if not nums:\n",
    "                return cnt\n",
    "            for i in range(len(nums)):\n",
    "                if nums[0] == temp:\n",
    "                    nums.pop(0)\n",
    "                else:\n",
    "                    break\n",
    "            for i in range(len(nums)):\n",
    "                if nums[i] == nums[0] + minus:\n",
    "                    nums[i] -= minus\n",
    "                else:\n",
    "                    break\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        counter_nums = Counter(nums)\n",
    "        res=0\n",
    "        for i in counter_nums:\n",
    "            if i != 0:\n",
    "                res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        return len(set(nums) - {0})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        return len({x for x in nums if x})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        tmp = 0\n",
    "        cou = 0\n",
    "        for i in range(0,len(nums)):\n",
    "            if nums[i] != tmp:\n",
    "                cou = cou + 1\n",
    "                tmp = nums[i]\n",
    "        return cou"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "         return len(set(nums) - {0})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        return len(set(nums)-{0})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "      heap = []\n",
    "      for n in nums:\n",
    "        if n > 0:\n",
    "          heapq.heappush(heap, n)\n",
    "\n",
    "      answer = 0\n",
    "      while heap:\n",
    "        top = heapq.heappop(heap)\n",
    "        arr = []\n",
    "        for i in range(len(heap)):\n",
    "          num = heap[i] - top\n",
    "          if num > 0:\n",
    "            arr.append(num)\n",
    "        heap = arr\n",
    "        heapq.heapify(heap)\n",
    "        answer += 1\n",
    "\n",
    "      return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        count = 0\n",
    "        cnt = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] - cnt > 0:\n",
    "                count += 1\n",
    "                cnt = nums[i]\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        print(nums)\n",
    "        res=set()\n",
    "        for num in nums:\n",
    "            if num!=0:\n",
    "                res.add(num)\n",
    "        return len(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        x = len(nums)\n",
    "        i = x - 1  # 从最后一个元素开始遍历\n",
    "        while i >= 0:\n",
    "            if nums[i] == 0:\n",
    "                nums.pop(i)\n",
    "            i -= 1\n",
    "        res = len(set(nums))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    每一次操作，都可以把数组 nums 中相同且非零的元素减少到 0，\n",
    "    因此，我们只需要统计数组 nums 中有多少个不同的非零元素，即为最少操作数。统计不同的非零元素，可以使用哈希表或数组来实现。\n",
    "\n",
    "    \n",
    "    '''\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        print(nums)\n",
    "        res=set()\n",
    "        for num in nums:\n",
    "            if num!=0:\n",
    "                res.add(num)\n",
    "        return len(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        cur=0\n",
    "        res=0\n",
    "        for i in nums:\n",
    "            if cur!=0:\n",
    "                if i>cur:\n",
    "                    res+=1\n",
    "                    cur=i\n",
    "            else:\n",
    "                if i==0:\n",
    "                    continue\n",
    "                else:\n",
    "                    cur=i\n",
    "                    res+=1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        count = 0\n",
    "        nums_sorted = sorted(nums,reverse = True) \n",
    "        mark_num = 0\n",
    "        i = 0\n",
    "        while i<len(nums_sorted):\n",
    "            if nums_sorted[i] != 0:\n",
    "                if nums_sorted[i] != mark_num:\n",
    "                    mark_num = nums_sorted[i]\n",
    "                    count += 1\n",
    "                    i += 1\n",
    "                else:\n",
    "                    i += 1\n",
    "            else:\n",
    "                break \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        k = 0\n",
    "        if nums == [0]*len(nums):\n",
    "            return 0\n",
    "        x = 0\n",
    "        while x != float('inf'):\n",
    "            for i in range(len(nums)):\n",
    "                if nums[i] == 0:\n",
    "                    nums[i] = float('inf')\n",
    "            x = min(nums)\n",
    "            for i in range(len(nums)):\n",
    "                nums[i] = nums[i] - x\n",
    "            k += 1\n",
    "        return k-1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        cnt = 0\n",
    "        while True:\n",
    "            num = next((i for i in nums if i > 0), 0)\n",
    "            if num == 0:\n",
    "                return cnt\n",
    "            nums = [j - num for j in nums if j > 0]\n",
    "            cnt += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        # 不相等的非负数数目\n",
    "        counter = set()\n",
    "        for num in nums:\n",
    "            if num != 0:\n",
    "                counter.add(num)\n",
    "        return len(counter)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        return len(set(x for x in nums if x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        #set(nums)  结果为{0, 1, 3, 5}  需要去掉已经为0的值\n",
    "        # print(set(nums) - {0})\n",
    "        return len(set(nums) - {0})\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        nums = [x for x in nums if x]\n",
    "        while nums:\n",
    "            mi = min(nums)\n",
    "            t = []\n",
    "            for x in nums:\n",
    "                if x - mi > 0:\n",
    "                    t.append(x - mi)\n",
    "            ans += 1\n",
    "            nums = t\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        if 0 in nums:\n",
    "            return len(set(nums))-1\n",
    "        return len(set(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:        \n",
    "        count=0\n",
    "        t=nums        \n",
    "        while True:            \n",
    "            x=[i for i in t if i!=0]\n",
    "            if x:\n",
    "                mint=min(x)\n",
    "            else:\n",
    "                break\n",
    "            y=[i-mint for i in x if i!=0]            \n",
    "            t=y            \n",
    "            count+=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        return len(set(nums)-{0})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        return len({x for x in nums if x})\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        return len(set(nums) - {0})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        count = 0\n",
    "        while len(nums) != 0:\n",
    "            for i in range(nums.count(0)):\n",
    "                nums.remove(0)\n",
    "            if len(nums) != 0:\n",
    "                nums_min = min(nums)\n",
    "                nums = [i - nums_min for i in nums]\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        \n",
    "        idx = -1\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] != 0:\n",
    "                idx = i\n",
    "                break\n",
    "\n",
    "        if idx == -1:\n",
    "            return 0\n",
    "\n",
    "        return len(set(nums[idx:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        return len({x for x in nums if x})\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        nums.sort()\n",
    "        while nums:\n",
    "            while nums and nums[0] == 0:\n",
    "                nums.pop(nums[0])\n",
    "                print(nums)\n",
    "            if not nums:\n",
    "                return res\n",
    "            tmp = nums[0]\n",
    "            for i in range(len(nums)):\n",
    "                nums[i] -= tmp\n",
    "                # print(nums)\n",
    "            # print(\"##################\")\n",
    "            # print(nums)\n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        let's make it more easier statement: to get the minium steps to make each element becomes 0 in given array.\n",
    "        and it needs to use the second smallest elements for the procesure.\n",
    "        So, kind of sorting techniques may be applied to do so.\n",
    "        \"\"\"\n",
    "\n",
    "        sorted_nums = sorted(nums)\n",
    "        steps = 0\n",
    "\n",
    "        while len(sorted_nums):\n",
    "            removed_zeros_nums = [n for n in sorted_nums if n != 0]\n",
    "            if len(removed_zeros_nums) == 0:\n",
    "                return steps\n",
    "            subtrahend = removed_zeros_nums[0]\n",
    "            subtrated_nums = [n - subtrahend for n in removed_zeros_nums]\n",
    "            sorted_nums = subtrated_nums\n",
    "            steps += 1\n",
    "        \n",
    "        return steps"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        length = len(nums)\n",
    "        count=0\n",
    "        nums.sort()\n",
    "        for i in range(length):\n",
    "            if nums[i]>0:\n",
    "                tmp=nums[i]                \n",
    "                for j in range(i,length):\n",
    "                    nums[j]-=tmp\n",
    "                count+=1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        reduce_number = 0\n",
    "        res = 0\n",
    "        for i, v in enumerate(nums):\n",
    "            v -= reduce_number\n",
    "            if v == 0:\n",
    "                continue\n",
    "            reduce_number += v\n",
    "            res += 1\n",
    "        return res\n",
    "        \n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        return len({x for x in nums if x})\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        length = len(nums)\n",
    "        count = 0\n",
    "\n",
    "        while True:\n",
    "            if len(list(filter(lambda x: x == 0, nums))) == length:\n",
    "                break\n",
    "            min_num = min(filter(lambda x: x > 0, nums))\n",
    "\n",
    "            for i in range(length):\n",
    "                if nums[i] > 0:\n",
    "                    nums[i] -= min_num\n",
    "\n",
    "            count += 1\n",
    "        \n",
    "        return count\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        return len(set(nums) - {0})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        return len(set(nums) - {0})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        nums = set(nums)\n",
    "        return len(nums) - 1 if 0 in nums else len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        return len(set(nums) - {0})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        cnt = 0\n",
    "        # nums[0] = 0\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "        if nums.count(0) == n:\n",
    "            return 0\n",
    "        ans = 0\n",
    "        while True:\n",
    "            while i<n and  nums[i] == cnt:\n",
    "                i += 1\n",
    "            if i < n:\n",
    "                ans += 1\n",
    "                cnt = nums[i]\n",
    "            elif i == n:\n",
    "                break\n",
    "        return ans\n",
    "            \n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        return len({x for x in nums if x})"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
